競プロ典型90問 004 Cross Sum
難易度順に取り組んでいく
愚直な解法
「同じ行または同じ列にあるマス（自分自身を含む）に書かれている整数をすべて合計した値」を全てのマスに対して計算する。
$ O(HW(H+W)) ~ $ (2 \times 10^3)^3 = 8 \times 10^9
制限時間が5秒なので、まあ間に合わなくもなさそうだ....けど結構危ない
あるマスとその右隣のマスを計算した時、同じ計算をしているところがある。
行ごとの和と列ごとの和をあらかじめ計算するとどうか？
行と列の和をそれぞれ参照した上で、一回余分に足された自身の要素を引くという戦略をとって解く。
code:cpp
for (size_t r = 0; r < H; r++) {
for (size_t c = 0; c < W; c++) {
}
}
短縮ポイント
row[r]とcolumn[r]（行ごとの和と列ごとの和）を計算するループを同じ1ループにまとめた。
この配列はAの全ての要素一つずつにアクセスすることになる。
足す場所を適切に分類さえできれば、同じループで処理できる
なお、キャッシュ的にはあんまり望ましくない。
アクセスが分散するため。